/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * 时间复杂度：O(nlogn)，空间复杂度是O(logn)-递归。归并排序的空间复杂度，因为数组要开辟额外空间，所以是O(n)
 * 自顶向下递归
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function (head) {
    return toSplitList(head, null)
};

const toSplitList = (head, tail) => {
    if (head === null) {
        return head
    }

    // tail交给右边的方法处理
    if (head.next === tail) {
        head.next = null
        return head
    }

    let slow = head,
        fast = head;

    // 根据快慢指针找到数组的中点，拆分链表进行归并
    while (fast !== tail) {
        slow = slow.next
        fast = fast.next
        if (fast !== tail) {
            fast = fast.next
        }
    }

    return merge(toSplitList(head, slow), toSplitList(slow, tail))
}

const merge = (left, right) => {
    let dummNode = new ListNode(0),
        head = dummNode,
        leftPoint = left,
        rightPoint = right;

    while (leftPoint !== null && rightPoint !== null) {
        if (leftPoint.val < rightPoint.val) {
            head.next = new ListNode(leftPoint.val)
            leftPoint = leftPoint.next
        } else {
            head.next = new ListNode(rightPoint.val)
            rightPoint = rightPoint.next
        }
        head = head.next
    }

    head.next = leftPoint ? leftPoint : rightPoint

    return dummNode.next
}




/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * 自底向上直接归并。不需要耗费额外的空间
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function (head) {
    if (head === null) return head

    let node = head, length = 0;
    while (node !== null) {
        node = node.next;
        length++
    }

    let dummyNode = new ListNode(0, head);
    // 第一轮：一个一个进行归并，得到两个两个排序好的链表
    // 第二轮：两个两个进行归并，得到四个四个排序号的链表
    for (let i = 1; i <= length; i*=2) {
        let prev = dummyNode, curr = dummyNode.next;

        while (curr !== null) {
            let node1 = curr
            for (let j = 1; j < i && curr.next !== null; j++) {
                curr = curr.next
            }
            let node2 = curr.next;
            // 切断node1的后续链
            curr.next = null;
            curr = node2;
            for (let j = 1; j < i && curr !== null && curr.next !== null; j++) {
                curr = curr.next
            }
            if (curr !== null) {
                let temp = curr.next;
                // 切断node2的后续链
                curr.next = null;
                curr = temp;
            }
            let mergeList = merge1(node1, node2)
            // 链接到原链表上,指针后移至链尾
            prev.next = mergeList
            while (prev.next !== null) {
                prev = prev.next
            }
        }
    }

    return dummyNode.next
}

const merge1 = (left, right) => {
    let dummNode = new ListNode(0),
        head = dummNode,
        leftPoint = left,
        rightPoint = right;

    while (leftPoint !== null && rightPoint !== null) {
        if (leftPoint.val < rightPoint.val) {
            head.next = leftPoint
            leftPoint = leftPoint.next
        } else {
            head.next = rightPoint
            rightPoint = rightPoint.next
        }
        head = head.next
    }

    head.next = leftPoint ? leftPoint : rightPoint

    return dummNode.next
}